#include <stdlib.h>
#include <time.h>

void Rand3(size_t startPos,size_t endPos, size_t &r1, size_t &r2, size_t &r3)
{
	int range= endPos- startPos+1;
	if(range<0)
	{
		printf("Error: endPos must greater than startPos\n");
		exit(1);
	}
	r1=rand()%range+startPos;
	r2=rand()%range+startPos;
	r3=rand()%range+startPos;
	while(r2==r1)
		r2=rand()%range+startPos;
	while(r3==r2 || r3==r1)
		r3=rand()%range+startPos;
}

template<typename T>
size_t Median3(T* vec ,size_t r1, size_t r2, size_t r3 )
{
	size_t largest=r1;
	size_t smallest=r1;
	if(vec[r2]>vec[largest])
		largest=r2;
	if(vec[r3]>vec[largest])
		largest=r3;
	if(vec[smallest]>vec[r2])
		smallest=r2;
	if(vec[smallest]>vec[r3])
		smallest=r3;
	if(smallest==largest)
		return smallest;
	if(r1!=smallest && r1!=largest)
		return r1;
	if(r2!=smallest && r2!=largest)
		return r2;
	if(r3!=smallest && r3!=largest)
		return r3;

}

template<typename T>
size_t PartitionRandMed(T* vec,size_t startPos, size_t endPos)
{
	size_t r1,r2,r3;
	size_t median;
	if(endPos-startPos+1>=3)
	{
		Rand3(startPos,endPos,r1,r2,r3);
		median=Median3(vec,r1,r2,r3);
	}
	else
		median=endPos;
	
	T pivot=vec[median];
	vec[median]=vec[endPos];;
	vec[endPos]=pivot;
	size_t i=startPos-1;
	for(size_t j=startPos;j<endPos;j++)
	{
		if(pivot>vec[j])
		{
			++i;
			T temp = vec[i];
			vec[i]=vec[j];
			vec[j]=temp;
		}
	}
	++i;
	T temp = vec[i];
	vec[i]=pivot;
	vec[endPos]=temp;
	return i;
}

template<typename T>
void _QuickSortRandMed(T *vec, size_t startPos, size_t endPos)
{
	if(startPos<endPos)
	{
		size_t middle = PartitionRandMed(vec, startPos,endPos);
		if(middle >startPos)
			_QuickSortRandMed(vec,startPos,middle-1);
		if(middle<endPos)
 			_QuickSortRandMed(vec,middle+1,endPos);
	}
}

template <typename T>
void QuickSortRandMed(T* vec, size_t cnt)
{
	srand((unsigned int)time(NULL));
	_QuickSortRandMed(vec,0,cnt-1);
}
